#include<bits/stdc++.h>
using namespace std;
int read(){
    char c=getchar();int x=0,f=1;
    while(!isdigit(c)&&c!='-') c=getchar();
    if(c=='-') f=-1;
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return f*x;
} 
const int N=2e3+10,M=2e5+10;
int T,n,a[M],h[M];
long long ans;
long long getsum(int l,int r){
    int sum=0;
    for(int i=l;i<=r;i++){
        for(int j=i-1;j>=l;j--){
            if(h[i]==h[j]){
                if(a[i]==a[j]) sum+=a[i];
                break;
            }
        }
    }
    return sum;
}
void dfs(int dep){
    if(dep>n){
        ans=max(ans,getsum(1,n));
        return;
    }
    h[dep]=0;dfs(dep+1);
    h[dep]=1;dfs(dep+1);
}
long long w[N][N],dp[N][N];
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    T=read();
    while(T--){
        //remember to clear
        n=read();ans=0;
        if(n<=15){
            for(int i=1;i<=n;i++)
            a[i]=read();
            dfs(1);
            cout<<ans<<endl;
            continue;
        }
        else if(n<=100){
            memset(dp,0,sizeof(dp));
            for(int i=1;i<=n;i++) a[i]=read();
            for(int i=1;i<=n;i++){
                for(int j=i;j<=n;j++){
                    w[i][j]=getsum(i,j);
                }
            }
            for(int len=1;len<n;len++){
                for(int l=1;l+len-1<=n;l++){
                    int r=l+len-1;
                    //dp[l][r+1]=? 
                    dp[l][r+1]=dp[l][r];
                    for(int k=l;k<=r;k++){
                        if(a[r+1]==a[k]){
                            dp[l][r+1]=max(dp[l][r+1],dp[l][k-1]+w[k+1][r]+a[r+1]);
                        }
                    }
                }
            }
            cout<<dp[1][n]<<endl;
            continue;
        }
        else{
            for(int i=1;i<=n;i++) a[i]=read();
            sort(a+1,a+n+1);
            for(int i=1;i<=n;i++){
                if(a[i+1]==a[i]) ans+=a[i];
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}